package deque;

import java.util.ArrayDeque;
import java.util.Deque;

public class finalPrices {
    public static void main(String[] args) {
        int[] prices = {10,1,1,6};
        finalPrices(prices);
    }

    public static int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for(int i=n-1 ; i>= 0 ;i--){
            while(!st.isEmpty() && prices[i] < prices[st.peek()]){
                st.pop();
            }
            if(st.isEmpty()){
                ans[i] = prices[i];
            }else{
                ans[i] = prices[i] - prices[st.peek()];
            }
            st.push(i);
        }
        return ans;
    }
}
